package com.gitee.feizns.explore.data_structure.tree.bs.mid;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 1305. 两棵二叉搜索树中的所有元素
 * @author feizns
 * @since 2020/3/17
 */
public class GetAllElements {

    public static void main(String[] args) {
        System.out.println(merge(Arrays.asList(1, 3, 5), Arrays.asList(2, 4, 6)));
    }

    public static List<Integer> getAllElements(TreeNode root1, TreeNode root2) {
        return merge(inOrder(root1, new LinkedList<>()), inOrder(root2, new LinkedList<>()));
    }

    private static List<Integer> merge(List<Integer> list, List<Integer> list2) {
        int i = 0;
        int j = 0;
        List<Integer> ret = new LinkedList<>();
        while ( i < list.size() || j < list2.size() ) {
            if ( i >= list.size() )
                ret.add(list2.get(j++));
            else if ( j >= list2.size() )
                ret.add(list.get(i++));
            else if ( list.get(i) < list2.get(j) )
                ret.add(list.get(i++));
            else
                ret.add(list2.get(j++));
        }
        return ret;
    }

    private static List<Integer> inOrder(TreeNode root, List<Integer> ret) {
        if ( root != null ) {
            inOrder(root.left, ret);
            ret.add(root.val);
            inOrder(root.right, ret);
        }
        return ret;
    }

}
